#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 图的邻接矩阵表示
typedef struct
{
    int vexnum;                                 // 顶点数
    int edges;                                  // 边数
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
} Graph;

// 全局访问标记数组
bool visited[MAX_VERTEX_NUM];

// 初始化图
void initGraph(Graph *G, int numVertices)
{
    G->vexnum = numVertices;
    G->edges = 0;

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; i++)
    {
        for (int j = 0; j < numVertices; j++)
        {
            G->matrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *G, int src, int dest)
{
    if (src >= 0 && src < G->vexnum && dest >= 0 && dest < G->vexnum)
    {
        G->matrix[src][dest] = 1;
        // 如果是无向图，取消下面这行的注释
        // G->matrix[dest][src] = 1;
        G->edges++;
    }
}

// 获取顶点v的第一个邻接顶点
int FirstNeighbor(Graph *G, int v)
{
    if (v < 0 || v >= G->vexnum)
        return -1;

    for (int i = 0; i < G->vexnum; i++)
    {
        if (G->matrix[v][i] == 1)
        {
            return i;
        }
    }
    return -1; // 没有邻接顶点
}

// 获取顶点v相对于w的下一个邻接顶点
int NextNeighbor(Graph *G, int v, int w)
{
    if (v < 0 || v >= G->vexnum || w < 0 || w >= G->vexnum)
        return -1;

    for (int i = w + 1; i < G->vexnum; i++)
    {
        if (G->matrix[v][i] == 1)
        {
            return i;
        }
    }
    return -1; // 没有下一个邻接顶点
}

// 访问顶点
void visit(int v)
{
    printf("访问顶点 %d ", v);
}

// 深度优先搜索
void DFS(Graph G, int v)
{
    visit(v);          // 访问顶点v
    visited[v] = true; // 设已访问标记

    // 遍历v的所有邻接顶点
    for (int w = FirstNeighbor(&G, v); w >= 0; w = NextNeighbor(&G, v, w))
    {
        if (!visited[w])
        {              // w为v的尚未访问的邻接顶点
            DFS(G, w); // 递归调用DFS
        }
    }
}

// 对整个图进行DFS遍历（处理非连通图）
void DFSTraverse(Graph G)
{
    // 初始化访问标记数组
    for (int v = 0; v < G.vexnum; ++v)
    {
        visited[v] = false; // 初始化已访问标记数据
    }

    printf("DFS遍历结果: ");

    // 本代码中是从v=0开始遍历
    for (int v = 0; v < G.vexnum; ++v)
    {
        if (!visited[v])
        {
            DFS(G, v);
        }
    }
    printf("\n");
}

// 打印图的邻接矩阵
void printGraph(Graph *G)
{
    printf("图的邻接矩阵:\n");
    printf("   ");
    for (int i = 0; i < G->vexnum; i++)
    {
        printf("%2d ", i);
    }
    printf("\n");

    for (int i = 0; i < G->vexnum; i++)
    {
        printf("%2d ", i);
        for (int j = 0; j < G->vexnum; j++)
        {
            printf("%2d ", G->matrix[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

// 主函数 - 测试用例
int main()
{
    Graph G;
    int numVertices = 6;

    // 初始化图
    initGraph(&G, numVertices);

    // 添加边 (构建一个示例图)
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 1, 4);
    addEdge(&G, 2, 5);
    addEdge(&G, 3, 5);

    printf("图的信息:\n");
    printf("顶点数: %d, 边数: %d\n\n", G.vexnum, G.edges);

    // 打印图的邻接矩阵
    printGraph(&G);

    // 进行DFS遍历
    DFSTraverse(G);

    printf("\n从特定顶点开始的DFS:\n");

    // 重置访问标记
    for (int i = 0; i < G.vexnum; i++)
    {
        visited[i] = false;
    }

    printf("从顶点0开始: ");
    DFS(G, 0);
    printf("\n");

    return 0;
}